package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * <p>
 * a02_组合
 * </p>
 *
 * @author flyduck
 * @since 2024-12-29
 */
public class a02_组合 {

    public static void main(String[] args) {
        a02_组合 a02_组合 = new a02_组合();
        List<List<Integer>> combine = a02_组合.combine(4, 2);
        System.out.println(combine);
    }

    public List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> resultList = new ArrayList<>();
        LinkedList<Integer> result = new LinkedList<>();

        traversal(resultList,result,n,k,1);
        return resultList;
    }

    public void traversal(List<List<Integer>> resultList,
                          LinkedList<Integer> result,
                          int n,
                          int k,
                          int startIdx){
        //终止条件
        if(result.size() == k){
            resultList.add(new ArrayList<>(result));
            return;
        }

        //单层搜索逻辑
        for (int i = startIdx; i <= n; i++) {
            result.add(i);//收集1
            System.out.println("traversal.add(i)========" + result);
            traversal(resultList, result, n, k, i + 1);//从2开始收集
            result.removeLast();
            System.out.println("traversal.removeLast()========" + result);
        }
    }

    public void traversal2(List<List<Integer>> resultList,
                          LinkedList<Integer> result,
                          int n,
                          int k,
                          int startIdx){
        //终止条件
        if(result.size() == k){
            resultList.add(new ArrayList<>(result));
            return;
        }

        //单层搜索逻辑
        for (int i = startIdx; i <= n; i++) {
            result.add(i);//收集1
            System.out.println("traversal2.add(i)========" + result);
            traversal3(resultList, result, n, k, i + 1);//从2开始收集
            result.removeLast();
            System.out.println("traversal2.removeLast()========" + result);
        }


    }

    public void traversal3(List<List<Integer>> resultList,
                           LinkedList<Integer> result,
                           int n,
                           int k,
                           int startIdx){
        //终止条件
        if(result.size() == k){
            resultList.add(new ArrayList<>(result));
            return;
        }

        //单层搜索逻辑
        for (int i = startIdx; i <= n; i++) {
            result.add(i);//收集1
            System.out.println("traversal3.add(i)========" + result);
            traversal3(resultList, result, n, k, i + 1);//从2开始收集
            result.removeLast();
            System.out.println("traversal3.removeLast()========" + result);
        }


    }

    public void traversal4(List<List<Integer>> resultList,
                           LinkedList<Integer> result,
                           int n,
                           int k,
                           int startIdx){
        //终止条件
        if(result.size() == k){
            resultList.add(new ArrayList<>(result));
            return;
        }

        //单层搜索逻辑
        for (int i = startIdx; i <= n; i++) {
            result.add(i);//收集1
            System.out.println("traversal4.add(i)========" + result);
            traversal4(resultList, result, n, k, i + 1);//从2开始收集
            result.removeLast();
            System.out.println("traversal4.removeLast()========" + result);
        }


    }

}
